

 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
  }
//力扣230. 二叉搜索树中第 K 小的元素
class Solution {
    private int i = 1;
    private int ans = 1;
    public int kthSmallest(TreeNode root, int k) {
        func(root,k);
        return ans;
    }
    public void func(TreeNode root,int k){
        if(root==null){
            return;
        }
        func(root.left,k);
        if((i++)==k){
            ans = root.val;
        }
        func(root.right,k);

    }
}


//力扣114. 二叉树展开为链表
 //迭代法:
class Solution1 {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // 找到左子树的最右节点（前驱节点）
                TreeNode predecessor = curr.left;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                // 把右子树接到前驱节点的右边
                predecessor.right = curr.right;
                // 把左子树移到右边，左指针置空
                curr.right = curr.left;
                curr.left = null;
            }
            curr = curr.right; // 继续处理下一个节点
        }
    }
}
//前序遍历法:
 //关键在于 Java 是值传递，但 TreeNode 是对象，所以 root 和 p 实际上操作的是同一块内存地址的数据。
class Solution3 {
    private TreeNode p = null; // 用于记录前一个节点
    public void flatten(TreeNode root) {
        func(root);
    }
    public void func(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先保存左右子树，防止递归修改后丢失
        TreeNode left = root.left;
        TreeNode right = root.right;

        if (p != null) {
            p.right = root; // 前一个节点的右指针指向当前节点
            p.left = null; // 左指针置空
        }
        p = root; // 更新 p 为当前节点

        func(left);  // 递归处理左子树
        func(right); // 递归处理右子树
    }
}